# LeetCode 567、字符串的排列
# 一、题目描述
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
提示：
1 <= s1.length, s2.length <= 104s1和s2仅包含小写字母
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
//
class Solution {
public boolean checkInclusion(String s1, String s2) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型
List<Integer> res = new ArrayList<>();
// 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
// needs 代表 p 中每个字符出现的频次
int[] needs = new int[26];
for(char ch : s1.toCharArray()){
// 对于数组类型，其下标为 int 类型
// 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
// 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
needs[ch - 'a']++;
}
// window 代表在滑动窗口中每个字符出现的频次
int[] window = new int[26];
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始
int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部
for(int end = 0; end < s2.length(); end++){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 获取此时将要加入到滑动窗口的元素
char cur = s2.charAt(end);
// 这个字符的频次需要发生变化
window[cur - 'a'] ++;
// 加入之后，去对比一下 window 中 cur 这个字符是否满足要求
if(isSame(window,needs)){
// 相同情况下，找到了满足条件的一个解，返回 true
return true;
}
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if( end >= s1.length() - 1 ){
// 4.2、更新 (部分或所有) 维护变量
char chr = s2.charAt(start);
// 最左端那个元素的频次发生变化
window[chr - 'a']--;
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start++;
}
}
// 【5、返回所需要的答案】
return false;
}
boolean isSame (int[] a, int [] b){
for(int i = 0; i < a.length; i++){
if(a[i] != b[i])return false;
}
return true;
}
}
# 2、C++ 代码
class Solution {
public:
bool checkInclusion(string s1, string s2) {
// 滑动窗口模板化解题，五步走策略
// 【1、定义需要维护的变量】
// 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型
vector<int> res;
// 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
// needs 代表 p 中每个字符出现的频次
vector<int> needs(26, 0);
for(auto& ch : s1){
// 对于数组类型，其下标为 int 类型
// 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
// 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
needs[ch - 'a']++;
}
// window 代表在滑动窗口中每个字符出现的频次
vector<int> window(26, 0);
// 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
// 窗口的左端位置从 0 开始
int start = 0;
// 窗口的右端位置从 0 开始，可以一直移动到尾部
for(int end = 0; end < s2.size(); end++){
// 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
// 获取此时将要加入到滑动窗口的元素
auto cur = s2[end];
// 这个字符的频次需要发生变化
window[cur - 'a']++;
// 加入之后，去对比一下 window 中 cur 这个字符是否满足要求
if(window == needs){
// 相同情况下，找到了满足条件的一个解，返回 true
return true;
}
// 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
// 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if( end >= s1.size() - 1 ){
// 4.2、更新 (部分或所有) 维护变量
auto chr = s2[start];
// 最左端那个元素的频次发生变化
window[chr - 'a']--;
// 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start++;
}
}
// 【5、返回所需要的答案】
return false;
}
};
# 3、Python 代码
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
# 滑动窗口模板化解题，五步走策略
# 【1、定义需要维护的变量】
# 题目要求返回这些子串的起始索引，因此使用数组来保存结果，存储的是整型
res = []
# 由于都是小写字母，因此直接用 26 个长度的数组代替原来的 HashMap ，比直接使用 HashMap 更优秀
# needs 代表 p 中每个字符出现的频次
needs = [0] * 26
# 开始统计 t 中每个字符出现的频次
for ch in s1:
# 对于数组类型，其下标为 int 类型
# 可以直接使用 char 类型变量，默认强制转换，存储的就是字母对应的 ASCII 码
# 比如 ch 是 b 字符，那么 b - a = 1，即 needs[1] 表示记录 b 出现的频次
idx = ord(ch) - ord('a')
needs[idx] += 1
# window 代表在滑动窗口中每个字符出现的频次
window = [0] * 26
# 【2、定义窗口的首尾端 (start, end)， 然后滑动窗口】
# 窗口的左端位置从 0 开始
start = 0
# 窗口的右端位置从 0 开始，可以一直移动到尾部
for end in range(len(s2)):
# 【3、更新需要维护的变量, 有的变量需要一个 if 语句来维护 (比如最大最小长度)】
# 获取此时将要加入到滑动窗口的元素
cur = s2[end]
# 这个字符的频次需要发生变化
window[ord(cur) - ord('a')] += 1
# 加入之后，去对比一下 window 中 cur 这个字符是否满足要求
if window == needs:
# 相同情况下，找到一个符合条件的索引
return True
# 【4、如果题目的窗口长度固定：用一个 if 语句判断一下当前窗口长度是否达到了限定长度 】
# 4.1、如果达到了，窗口左指针前移一个单位，从而保证下一次右指针右移时，窗口长度保持不变,
if end >= len(s1) - 1 :
# 4.2、更新 (部分或所有) 维护变量
chr = s2[start]
# 最左端那个元素的频次发生变化
window[ord(chr) - ord('a')] -= 1
# 4.3、窗口左指针前移一个单位保证下一次右指针右移时窗口长度保持不变
start += 1
# 【5、返回所需要的答案】
return False